//
// Created by ASUS on 2024/7/24/星期三.
//
#include <bits/stdc++.h>
using namespace std;


class TreeAncestor {
	map<pair<int,int>, int> lca;
public:
	TreeAncestor(vector<vector<int>> &edges) {
		int n = edges.size() + 1;
		vector<vector<int>> g(n);
		for (auto &e: edges) {
			int x = e[0], y = e[1];
			g[x].push_back(y);
			g[y].push_back(x); // 建树
		}
		// 并查集模板
		vector<int> root(n);
		iota(root.begin(), root.end(), 0);
		function<int(int)> find = [&](int x) -> int { return root[x] == x ? x : root[x] = find(root[x]); };

		vector<int> diff(n), father(n), color(n);
		function<void(int, int)> tarjan = [&](int x, int fa) {
			father[x] = fa;
			color[x] = 1; // 递归中
			for (int y: g[x]) {
				if (color[y] == 0) { // 未递归
					tarjan(y, x);
					root[y] = x; // 相当于把 y 的子树节点全部 merge 到 x
				}
			}
			//这里要读入查询
			for(int i=0;i<n;i++){
				if(x<=i)
					lca[{x,i}]=find(i);
				else
					lca[{i,x}]=find(i);
			}
			color[x] = 2; // 递归结束
		};
		tarjan(0, -1);
	}

	int getLCA(int u, int v) {
		if(u>v) swap(u,v);
		return lca[{u,v}];
	}
};